Phil Zimmermann tạo ra phiên bản PGP đầu tiên vào năm 1991. Vào thời điểm này, ông ta đã là một nhà hoạt động chống năng lượng hạt nhân và mục đích tạo PGP là để phục vụ những người có mục tiêu tương tự có thể sử dụng các hệ thống bảng thông báo điện tử (bulletin board) và lưu trữ tệp một cách an toàn. Đối với mục tiêu sử dụng phi thương mại, PGP hoàn toàn miễn phí và toàn bộ mã nguồn được bao gồm trong tất cả sản phẩm. PGP dễ dàng thâm nhập vào Usenet và từ đó vào Internet.

Cái tên "Pretty Good Privacy" (tạm dịch: Bí mật tương đối tốt) được đặt theo tên của một cửa hiệu tạp hóa ở thành phố giả tưởng Lake Wobegon trong chương trình trên radio của tác giả Garrison Keillor. Trong chương trình, tên của hiệu tạp hóa là "Ralph's Pretty Good Grocery".

Ngay từ khi mới xuất hiện, PGP đã vướng vào chính sách hạn chế xuất khẩu phần mềm mật mã của chính phủ Hoa Kỳ.

Sự phổ biến của PGP thời kỳ đầu

Ngay sau khi xuất hiện, PGP đã thu hút được khá nhiều người sử dụng trên Internet. Những người sử dụng và ủng hộ bao gồm những người bất đồng quan điểm tại những nước chuyên chế, những người bảo vệ quyền tự do cá nhân và những người ủng hộ tự do thông tin (cypherpunk).

Không lâu sau khi ra đời, PGP đã được sử dụng bên ngoài Hoa Kỳ và vào tháng 2 năm 1993, Zimmermann trở thành mục tiêu của một cuộc điều tra của chính phủ Hoa Kỳ về việc xuất khẩu "vũ khí" không có giấy phép. Tại thời điểm đó, các hệ thống mật mã với khóa lớn hơn 40 bít được xếp hạng cùng với vũ khí trong khi PGP chưa bao giờ sử dụng khóa có độ dài nhỏ hơn 128 bít. Mức hình phạt cho tội nói trên khá nặng nhưng cuộc điều tra đã đột ngột dừng lại mà không có một lời kết tội nào.

Chính sách hạn chế xuất khẩu mật mã vẫn còn hiệu lực nhưng đã được nới lỏng rất nhiều kể từ thập kỷ 1990. Từ năm 2000 trở đi thì việc tuân thủ các chính sách này không còn là điều khó khăn nữa. PGP không còn được xếp là vũ khí không được phép xuất khẩu và được phép xuất khẩu tới bất kỳ nơi nào nếu không bị cấm tại nơi đó.

Bằng sáng chế

Các phiên bản PGP đầu tiên còn gặp phải vấn đề về bằng sáng chế. Phiên bản đầu tiên sử dụng một thuật toán mã hóa khóa đối xứng do chính Zimmermann thiết kế (có tên là Bass-O-Matic). Ngay sau đó, ông ta thấy được thuật toán này không đảm bảo an ninh và thay thế bằng IDEA. Cả hai thuật toán RSA và IDEA đều đã được cấp bằng sáng chế và đòi hỏi có bản quyền để sử dụng. Đã có những tranh cãi khá gay gắt về việc Zimmermann sử dụng RSA và IDEA trong phần mềm của mình. Zimmermann tuyên bố rằng RSA Data Security (nay là RSA Security) đã cho phép (bằng lời nói) đối với việc sử dụng cho các mục đích phi thương mại nhưng RSA không thừa nhận việc này. Cuộc điều tra đã bắt đầu từ đơn kiện của RSADSI tới hải quan Hoa kỳ về việc sử dụng thuật toán RSA trong PGP.

Vấn đề còn trở nên phức tạp hơn do tình trạng về bản quyền khác nhau ở các quốc gia. RSA chỉ được cấp bằng sáng chế tại Hoa Kỳ; những người nắm bản quyền IDEA tỏ ra rộng rãi hơn so với RSA. Thêm vào đó, bản quyền của thuật toán RSA được kiểm soát một phần bởi MIT thông qua RSADSI (RSA Data Security, Inc.). MIT không phải đối PGP nhưng gặp khó khăn do thái độ thù địch của RSADSI đối với các sử dụng phi thương mại của RSA.

Tranh chấp về bản quyền RSA được giải quyết bằng việc phát triển PGP theo hai nhánh:

• Phiên bản sử dụng trong Hoa Kỳ: sử dụng thư viện RSAREF (shareware của RSA).
• Phiên bản quốc tế: PGP-i, sử dụng mã RSA nguyên gốc của Zimmermann. Điều này cũng giúp tránh những khó khăn với quy chế hạn chế xuất khẩu phần mềm mật mã. PGP-i được duy trì và phân phối bởi Ståle Schumacher ở Na Uy.

Phiên bản dành cho Hoa Kỳ được phân phối bởi nhiều nhà cung cấp, trong đó bao gồm cả MIT trên Internet, BBS, và các cá nhân và nhóm người dùng. Ít nhất là trên website của MIT, để nhận được PGP thì địa chỉ email phải thuộc về Hoa Kỳ hoặc Canada. Bên ngoài Hoa Kỳ, người sử dụng download từ trang web của Schumacher: pgpi.org.